/**
 * 链表-删除链表倒数第n个元素-力扣19
 */
public class Practice_34 {
    public static void main(String[] args) {
        ListNode head = new ListNode();
        head.val = 2;

        ListNode second = new ListNode();
        second.val = 3;
        head.next = second;


        ListNode third = new ListNode();
        third.val = 4;
        head.next.next = third;

        ListNode four = new ListNode();
        four.val = 5;
        head.next.next.next = four;

        ListNode five = new ListNode();
        five.val = 6;
        head.next.next.next.next = five;

        ListNode list = removeNthFromEnd(head,5);
    }

    public  static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode imghead = new ListNode();//虚拟头节点
        imghead.next = head;//连接虚拟头节点和后续节点

        ListNode fast = imghead;//快慢指针放到虚拟头节点
        ListNode slow = imghead;//快慢指针放到虚拟头节点

        int istep = n + 1;
        while (fast != null && istep>0) {//快指针先走n+1步；  注意这里两个条件
            fast = fast.next;
            istep = istep - 1;
        }

        while(fast!=null){//快慢指针按同样步数走，遇到快指针到尾部时停止
            fast=fast.next;//快指针每次移动一步
            slow=slow.next;//慢指针每次移动一步
        }

        ListNode tmp=slow.next.next;
        slow.next=null;//断开与下个节点的连接
        slow.next=tmp;//连到下下个节点


        return imghead.next;//注意返回这个
    }

    static class ListNode {
        private int val;
        private ListNode next;
    }
}
